package info.mikrotubula.utils;


public class Sort {

    /**
	 *
	 * @param a - array to find median in
	 * @param end - last index
	 * @param median - index of median [l <= k < n]
	 * @return average value
	 */
	public int hoarSort(int[] a, int end, int median) {

		int n,i,j,k,w;
		int c[] = a;

		n = end+1;
		w = median;

        // algorytm Hoare'a
		i=0;
		j=n-1;
		n=w;
		while (i!=j)
			{
		        k=partition(c,i,j);
		        k=k-i+1;
		        if (k>=w) j=i+k-1;
		        if (k<w) {
		        	w-=k;
		            i+=k;
                }
			}
		return c[i];

	}

	public int partition(int c[], int a, int b) {
		int e,tmp;
		e=c[a];        //elemennt dzielacy
		while (a<b)
		        {
		        while ((a<b) && (c[b]>=e)) b--;
		        while ((a<b) && (c[a]<e)) a++;
		        if (a<b)
		                {
		                tmp=c[a];
		                c[a]=c[b];
		                c[b]=tmp;
		                }
		        }
		return a;
	}

}
